package com.singzi.leetcode.N300;

public class T0279 {
    public static void main(String[] args) {
        Solution00279 solution00279 = new Solution00279();
        System.out.println(solution00279.numSquares(100));
    }
}
class Solution00279 {
    static int min;
    static int cont;
    public int numSquares(int n) {
        int max_sqrt = (int)Math.sqrt(n);
        int []nums = new int[max_sqrt];
        for(int i = 0;i < max_sqrt;i++){
            nums[i] = (i+1)*(i+1);
        }
        min = n;
        cont = 0;
        backTrace(nums, 0, 0, n);
        return min;
    }

    private void backTrace(int[] nums, int index, int sum, int n) {
//        if(sum > n) return;
        if(sum == n){
            if(cont < min){
                min = cont;
            }
            return;
        }
        for (int i = index; i < nums.length; i++) {
            if(sum > n) break;
            cont++;
            backTrace(nums, i, sum+nums[i], n);
//            sum -= nums[i];
            cont--;
        }
    }
}